/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

https://leetcode.cn/problems/reorder-list/
class Solution {
public:

    ListNode* FindMid(ListNode* head)
    {
        ListNode* fast=head,*slow=head;
        while(fast&&fast->next)
        {
            fast=fast->next->next;
            slow=slow->next;
        }
        return slow;
    }

    ListNode* Reverse(ListNode*mhead)
    {
        ListNode* newhead=new ListNode();
        ListNode*cur=mhead->next;
        mhead->next=nullptr;//断开
        //头插
        while(cur)
        {
            ListNode*next=cur->next;
            cur->next=newhead->next;
            newhead->next=cur;
            cur=next;
            
        }
        cur=newhead->next;
        delete newhead;
        return cur;
    }
    void reorderList(ListNode* head) {
        ListNode* mid=FindMid(head);
        ListNode* head2=Reverse(mid);

        ListNode*newhead=new ListNode();
        ListNode *cur1=head,*cur2=head2,*prev=newhead;
        while(cur1)
        {
            prev->next=cur1;
            prev=prev->next;
            cur1=cur1->next;
            if(cur2)
            {
                prev->next=cur2;
                prev=prev->next;
                cur2=cur2->next;
            }
        }
        delete newhead;
    }
};